package tree.递归;

import po.TreeNode;

import java.util.HashMap;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 重建二叉树.java
 * @Description TODO
 * @createTime 2021年01月24日 11:07:00
 */
public class 重建二叉树 {
    /**
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字
     **/

    //保存中序遍历
    HashMap<Integer, Integer> map = new HashMap<>();
    int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < preorder.length; i++) {
            map.put(inorder[i], i);
        }
        return recursive(0, 0, inorder.length - 1);
    }

    private TreeNode recursive(int root, int left, int right) {
        if (left > right) {
            return null;
        }
        //先找出根节点   3
        TreeNode rootNode = new TreeNode(preorder[root]);
        //获取出根节点在中序遍历的index
        Integer rootIndex = map.get(rootNode.val);
        /**
         * 切分出左子树
         * 左子树的根节点：根节点= 前序遍历根节点的位置+1 ，也就是pre_root_idx+1
         * 左子树的左子树：
         * 左子树的右子树：在中序遍历中是根节点的索引-1，
         */
        rootNode.left = recursive(root + 1, left, rootIndex - 1);
        //切分出由子树,右子树的跟是前序遍历的跟节点位置加上左子树的个数（也就是中序遍历中跟节点前面元素的个数）
        //中序遍历的中左子树的长度= 左子树的左边(rootIndex-1) - 右边(left+1)
        rootNode.right = recursive(root + (rootIndex - 1 - left + 1), rootIndex + 1, right);
        //切分右子树
        return rootNode;
    }
}
